第一次刷 LeetCode 就撞牆

leetcode

gigd123 2021-09-12 01:34:17 ‧ 1980 瀏覽

分享至

一切都是為了面試

這只是一篇單純的心得整理，先說說為何我要刷 LeetCode，~~因為聽說下周的一場面試會考啊(我就是如此的膚淺)~~，所以我就想說來簡單刷個一兩題也好，不然原本是想說先看完一個邏輯訓練的課程後，再來刷 LeetCode。這邊先推薦一下 Lidemy 的一門課程先別急著寫 leetcode，非常適合像我這種非本科系出生，邏輯又不算好的工程師，這門課程會帶著你去刷很多相對 LeetCode 來說簡單很多的題目，同時也會講解題目和解答的邏輯，我覺得對提升自己的程式邏輯有不小的幫助。

什麼是 Hash Table

總之，逼不得已的在今天第一次碰了 LeetCode，並選了難度 Easy 的第一題， Two Sum，題目會給予一組 array，裡面會有一些 number，然後會給一個 number target，我們必須找出 array 中任兩個加總為 target 的數值，並回傳他們的 index。

看完題目解說後，很有自信地用兩個 for 迴圈去解題，然後直接撞牆，遇上了維特大大這篇文章一樣的情境刷 LeetCode 該有的基本知識，然後我也參考了他的文章去找解答，於是看到了像是 Hash Table、時間複雜度之類的神奇事物，在網路上搜尋了文章之後，覺得資訊量一下爆炸，逼不得已，只好來做紀錄。

一般來說我們儲存多筆資料，是用 array 來處理，當我們要比對某一筆資料是否存在於 array 裡面時，最直覺的做法就是直接 for 迴圈跑 array，直到找到一樣的資料。這總做法跟我在Two Sum一開始所想的兩個 for 迴圈的作法一樣，如果 n 越大，兩個迴圈相對就要執行越多次步驟。而 hashtable 則不一樣，JS 中 hashtable 的作法是用物件的方式儲存資料的 key 和 value，這樣我們在對比資料時，只要呼叫 key 就能馬上取得資料。

在Two Sum裡，hashtable 的作法，是只跑一遍迴圈，我們以下面資料為例，我們要在 nums array 中找到加起來為 9 的兩個數字，並回傳他們的 index。

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
當迴圈跑到 nums[0] 的時候，我們就儲存 data 2 和它的 index 0 到物件中

let number = { 2:0 }

然後繼續跑回圈，每一個迴圈我們都去比對 target - nums[i] 的值是否已經儲存在資料裡了，如果已經存在，就表示這一個 nums[i] 和物件中已經儲存的資料是我們想要的答案。

var twoSum = function(nums, target) {
    const dataObj = {}
    for (let i = 0; i < nums.length; i++) {
        // 如果 dataOnj[nums[i]] 有數值且大於等於 0，那這筆資料和目前的 index 就是我們要回傳的答案
        // 以題目為例到迴圈第二次執行時， dataObj 裡面應該是 { 7:0 }
        // 所以 dataObj[nums[i]] 為 0`,符合條件，return 答案
        if ( dataObj[nums[i]] >= 0) {
            return [dataObj[nums[i]], i]
        }
        // 用 target 減去當前的 nums[i]，將得到的數字做為 key，index 作為 value，以題目為例，第一筆存入的會是 7:0
        dataObj[ target - nums[i]  ] = i
    }
};